package huaweiOD;

/**
 * 停车场车辆统计
 * 在一个特定大小的停车场中，使用数组cars[]来表示车辆的分布情况。其中，数组中的值1表示有车，0表示没有车。车辆的大小不一，小车占一个车位（长度1），货车占两个车位（长度2），
 * 卡车占三个车位（长度3）。目标是统计停车场最少可以停多少辆车，并返回具体的数目。
 *
 * 输入描述：
 *
 * 输入为一个整型字符串数组cars[]，其中1表示有车，0表示没车。数组的长度小于1000。
 *
 * 输出描述：
 *
 * 输出为一个整型数字字符串，表示最少停车数目。
 *
 * 示例1：
 *
 * 输入：1,0,1
 * 输出：2
 * 说明：1个小车占第1个车位，第二个车位空；1个小车占第3个车位。最少有两辆车。
 *
 * 示例2：
 *
 * 输入：1,1,0,0,1,1,1,0,1
 * 输出：3
 * 说明：1个货车占第1、2个车位，第3、4个车位空；1个卡车占第5、6、7个车位，第8个车位空；1个小车占第9个车位。最少3辆车。
 *
 * 思路；这道题使用动态规划最好解决，因为  小车占1 ， 货车占11， 卡车占111， 所以通过动态规划，
 * 我们可以使用动态规划的方法来解决这个问题。定义一个数组dp，其中dp[i]表示到第i个车位最少需要多少个停车位。初始化时，第0个车位不需停放车辆，所以dp[0]为0或1。
 *
 * 然后，从第1个车位开始遍历。如果第i个车位有车（cars[i] == 1），我们需要考虑两种情况：
 *
 * 如果第i-1个车位也有车（cars[i-1] == 1），那么第i个车位可以停放在第i-1个车位后面，需要一个停车位，即dp[i] = dp[i-1] + 1。
 * 如果第i-1个车位没有车（cars[i-1] == 0），那么第i个车位可以停放在空位上，根据车辆长度计算需要多少个停车位。如果第i-2个车位有车，
 * 那么可以选择停放在第i-2个车位后面，需要一个停车位；如果第i-2个车位没有车，那么可以选择停放在第i-3个车位后面，需要两个或三个停车位。
 * 即dp[i] = dp[i-2] + (i % 3 == 0 ? 3 : i % 3 == 1 ? 2 : 1)。
 *
 * 如果第i个车位没有车（cars[i] == 0），那么不需要额外的停车位，即dp[i] = dp[i-1]。
 *
 * 最后，返回dp数组的最后一个元素，即为最少停车数目。
 *
 * 思路：动态规划就是通过判断当前位与dp[i-1]的情况，对于此题来讲，就是判断第i位有没有车.
 *
 */
public class Car_001 {

    public static void main(String[] args) {

    }

    public static int carParking(int[] cars) {
        if (cars.length == 0) {
            return 0;
        }
        int dp[] = new int[cars.length];
        dp[0] = cars[0] == 1 ? 1:0;
        for (int i = 1; i < cars.length; i++) {
            if(cars[i] == 1){ // 第i位有车
                // 如果car[i-1] 位有车
                if(cars[i-1] == 1){ // 则 i位 有车就新加一位车
                    dp[i] = dp[i-1] + 1;
                }else {  // car [i-1] 没车
                    dp[i] = dp[i-2] + (i % 3 == 0 ? 3 : i % 3 == 1 ? 2 : 1);
                }
            }else { // 第i位没车
                dp[i] = dp[i-1];
            }
        }
        return dp[cars.length-1];
    }

}
